package org.cabbage.lintcode;

/**
 * 设计一个算法，找出只含素因子2，3，5 的第 n 小的数。
 * <p>
 * 符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
 * <p>
 * 注意事项
 * <p>
 * 我们可以认为1也是一个丑数
 * <p>
 * 您在真实的面试中是否遇到过这个题？ Yes
 * 样例
 * 如果n = 9， 返回 10
 * <p>
 * 要求时间复杂度为O(nlogn)或者O(n)
 *
 * @author gezhangyuan
 */
public class Ugly {

    public static void main(String[] args) {
        System.out.println(nthUglyNumber(10));
    }

    public static int nthUglyNumber(int n) {
        // Write your code here
        int[] u = new int[n];
        u[0] = 1;
        int u2 = 0, u3 = 0, u5 = 0;
        for (int i = 1; i < n; i++) {
            u[i] = min(min(u[u2] * 2, u[u3] * 3), u[u5] * 5);
            if ((u[i] / u[u2]) == 2) u2++;
            if ((u[i] / u[u3]) == 3) u3++;
            if ((u[i] / u[u5]) == 5) u5++;
        }
        return u[n - 1];
    }

    public static int min(int a, int b) {
        return a < b ? a : b;
    }

}
